1. Field of the Invention
This invention relates to a pipeline processor which is a data processor for executing a sequential instruction stream by use of a pipeline processing system, and more particularly to an instruction controlling method and apparatus in a pipeline processor for independently processing instruction fetch and instruction execution in a pipeline fashion, previously predicting a branching destination (target) by a branch instruction based on branch history which is history information of the result of past execution of branch instruction, and fetching an instruction string of the branching destination before completion of the branch instruction execution.
2. Description of the Related Art
A pipeline processor is a data processor utilizing a pipeline processing system for executing a sequential instruction stream. In the pipeline processor, if an execution stage becomes available when one instruction is executed in the instruction execution process, a next instruction is applied to the available stage and execution of the next instruction is started even if execution of the preceding instruction is not completed. Thus, in the pipeline processor, an attempt is made to enhance the performance by sequentially applying instructions and starting execution of the instructions if an execution stage becomes available without waiting for completion of the individual instruction execution in the process of executing sequential instructions.
However, the result of execution of the preceding instruction often gives an influence on execution of the succeeding instruction, and in this case, it is necessary to wait for execution of the preceding instruction before starting execution of the succeeding instruction, thus causing disorder in the pipeline. The disorder of the pipeline may cause the performance of the pipeline to be lowered.
Particularly, in the branch instruction, whether the branch is taken or not and the address of an instruction of a branching destination cannot be determined until the branch instruction execution is completed. That is, when a fetched instruction is a branch instruction, whether the branch is taken or not cannot be determined before the branch instruction is executed, and therefore, the address of an instruction of a branching destination based on the result of execution of the branch cannot be determined prior to execution of the branch instruction. The branch instruction naturally causes disorder in the pipeline. The frequency of occurrence of the branch instruction is high and most likely causes degradation of the performance of the pipeline processor.
In order to alleviate the degree of disorder of the pipeline due to the branch instruction, for example, it is considered to enhance the efficiency of the pipeline process by storing the relation between control information as to whether the branch is taken or not, the instruction address of the branch instruction, and the "branching-destination" address which is an instruction address of the branching destination into a memory as history information called branch history, for example, predicting the result of execution of the branch instruction based on past history information registered in the branch history, prefetching the instruction of the branching destination, and applying the fetched instruction to an instruction execution stage following the branch instruction. That is, when the above mechanism is utilized, whether the branch is taken or not and a corresponding branching-destination address are previously predicted based on the history of the result of past execution registered in the branch history prior to execution of the branch instruction or completion thereof and instruction fetch is effected by use of the predicted branching-destination address according to the predicted result of the branch to supply the fetched instruction to the instruction execution stage following the branch instruction.
A case wherein the branch is taken, a branch instruction is contained in a branching-destination instruction string, and a branch is taken in the branch instruction may be sometimes provided as the result of execution of the branch instruction. Such a case occurs mainly in a process in which different instruction strings are sequentially executed by jumps by branch instructions, but it occurs not only in the above process, but also in a case wherein a jump of several instructions is made by a conditional branch to selectively effect a process and a case wherein a jump is made to the head instruction of the instruction string in which the branch instruction is present to form a loop, for example, and such cases are naturally expected to occur in general processes.
In the above case, it is easily supposed that the instruction fetch of a branching destination of a branch instruction is effected by use of a branching-destination address obtained from the branch history prior to execution of the branch instruction itself and a branching-destination address of a next branch instruction can be derived from the branch history by the instruction fetch.
However, in order to fetch the instruction string of the branching destination by use of the branching-destination address obtained from the branch history prior to execution of the branch instruction, a mechanism for holding the fetched instruction string, for example, instruction buffer is necessary. Such an instruction buffer has a limitation in its capacity, and generally cannot hold a large number of instruction strings. Therefore, fetch of the instruction strings of the branching destination based on information obtained from the branch history cannot be effected limitlessly.
Further, when taking the efficiency of usage of the instruction buffer into consideration, it is desirable to effect the fetch of the instruction strings of the branching destination based on the branch history only when the possibility that the instruction string to be prefetched will be actually used is determined to be high as the result of execution of the branch. When the possibility that the instruction string to be prefetched will be actually used is determined to be high as the result of execution of the branch as described before, the effect of the branch history is significantly lowered if fetch of the instruction string of a branching destination of a next branch instruction cannot be effected based on information of the branch history.